UVa/10130 - SuperSale/10310.cpp

   1 /*
   2   10310 - SuperSale
   3   UVa Online Judge
   4
   5   Andrés Mejía-Posada
   6   Accepted
   7  */
   8 #include <algorithm>
   9 #include <iostream>
  10 #include <cassert>
  11
  12 using namespace std;
  13
  14 const int MAXC = 30, MAXN = 1000;
  15
  16 /*
  17   Classical 0-1 knapsack.
  18   dp[i][j] = Using first i objects, maximum value that can be selected not exceeding weight j.
  19  */
  20
  21 int dp[MAXN][MAXC+1];
  22
  23 int main(){
  24   int T;
  25   cin >> T;
  26   while (T--){
  27     int n;
  28     cin >> n;
  29     int w[n], v[n];
  30     for (int i=0; i<n; ++i){
  31       cin >> v[i] >> w[i];
  32       assert(1 <= v[i] && v[i] <= 100);
  33       assert(1 <= w[i] && w[i] <= 30);
  34     }
  35
  36     for (int j=0; j<=MAXC; ++j){
  37       dp[0][j] = (j < w[0] ? 0 : v[0]);
  38     }
  39
  40     for (int i=1; i<n; ++i){
  41       dp[i][0] = 0;
  42       for (int j=1; j<=MAXC; ++j){
  43         dp[i][j] = dp[i-1][j];
  44         if (j - w[i] >= 0){
  45           dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
  46         }
  47       }
  48     }
  49
  50     int g, c, answer = 0;
  51     cin >> g;
  52     while (g--){
  53       cin >> c;
  54       assert(1 <= c && c <= 30);
  55       answer += dp[n-1][c];
  56     }
  57     assert(answer > 0);
  58     cout << answer << endl;
  59   }
  60   return 0;
  61 }